#include <iostream>
#include <vector>
#include "UnionFind.h"

using namespace std;

// O(eloge) + O(elogv)
template <typename Graph, typename Weight>
class KruskalMST{

private:
    vector<Edge<Weight>> mst;		// 最小生成树
    Weight mstWeight;				// 相应的权值

public:
    KruskalMST(Graph &graph){

		// 使用最小堆排序,方便按从小到大顺序取出边
		// 拥有图相应边个数空间,每个里面存储相应边
        MinHeap<Edge<Weight>> pq( graph.E() );
        for( int i = 0 ; i < graph.V() ; i ++ ){	// 遍历所有的顶点
            typename Graph::adjIterator adj(graph,i);
			// 遍历顶点所有邻边
            for( Edge<Weight> *e = adj.begin() ; !adj.end() ; e = adj.next() )
				// 针对无向图, 防止存储两边相同边
                if( e->v() < e->w() )
                    pq.insert(*e);
        }

		// 并查集开辟顶点个数的空间
        UnionFind uf = UnionFind(graph.V());
		// 最小堆不为空，最小生成树个数小于 v-1
        while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){

			// 取出最小堆中最短的那条边
            Edge<Weight> e = pq.extractMin();
			// 判断 e.v e.w 是否已经连在一起,已经连在一起不考虑
            if( uf.isConnected( e.v() , e.w() ) )
                continue;

            mst.push_back( e );					// 将边放进最小生成树
            uf.unionElements( e.v() , e.w() );  // 将最小生成树两点 union
        }

        mstWeight = mst[0].wt();
        for( int i = 1 ; i < mst.size() ; i ++ )
            mstWeight += mst[i].wt();
    }

    ~KruskalMST(){

    }

    vector<Edge<Weight>> mstEdges(){
        return mst;
    };

    Weight result(){
        return mstWeight;
    };
};
